package server.simple100;


import org.junit.Test;

import java.util.Arrays;

/***
 * 88. 合并两个有序数组
 * <P>
 *     容易错在细节
 *     1、nums1 或 m为null， 不能直接 nums1 = nums2， 数组引用只能改变内部，不能直接改变本身
 *     2、增加数据时, nums1不是绝对的有序, 后面包含了 容纳 nums2的索引位置，默认全为0
 *     3、增加数据时, nums1不是绝对的有序, 后面包含了 容纳 nums2的索引位置，
 *        每次成功添加后一个数后需要重新计算nums1长度
 *     4、m 无法在子方法中直接改变值, 同nums1 只能改变内部，不能直接改变本身, m只有本身
 * </P>
 */
public class LeetCode88 {


    @Test
    public void test() {
        int[] nums1 = {1,0};
        int[] nums2 = {2};
        merge(nums1, 1, nums2, 0);
        System.out.println(Arrays.toString(nums1));
    }

    /**
     *   1、写一个添加方法add, 并判断大小插入到指定位置
     *      1.1、找到插入位置后让指定索引后的数据全部后移一位
     *      1.2、重新计算 nums1 的长度 m
     *
     *   2、遍历nums2依次插入
     *
     *   3、操作前两部前判断 nums1 是否为null 和 nums2 是否为null
     *
     * @param nums1
     * @param m
     * @param nums2
     * @param n
     */

    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // nums2
        if (m == 0) {
            for (int i = 0; i < nums2.length; i++) {
                nums1[i] = nums2[i];
            }
            return;
        }
        if (nums2.length == 0) {
            return;
        }
        for (int i = 0; i < nums2.length; i++) {
            m = add(nums1, nums2[i], m);
        }
    }


    /**
     * 插入数据到 大于等于上一位数的位置和小于等于下一位数的位置, 暂不考虑 nums1 插入到最后一位的问题
     * @param nums1
     * @param val
     */
    public int add(int[] nums1, int val, int m) {
        for (int i = nums1.length-1 ; i >= 0; i--) {
//            1 3 5  7  9
//                      10
            // 插入到索引0
            if (val < nums1[0]) {
                for (int j = nums1.length-1 ; j > 0; j--) {
                    nums1[j] = nums1[j - 1];
                }
                nums1[0] = val;
                return m + 1;
            }
            // 插入到指定索引位置
            int mv = i - m;
            if (val >= nums1[i] && mv < 0) {
                // 当前索引+1 的数据全部后移一位,
                // 插入值放入当前索引+1, j=插入位置
                for (int j = nums1.length-1; j > i + 1; j--) {
                    nums1[j] = nums1[j - 1];
                }
                nums1[i + 1] = val;
                // 变更nums1 的长度
                return m + 1;
            }
        }
        return m;
    }
}

//
//
// 给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。
//
//        初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 的空间大小等于 m + n，这样它就有足够的空间保存来自 nums2 的元素。
//
//         
//
//        示例 1：
//
//        输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
//        输出：[1,2,2,3,5,6]
//        示例 2：
//
//        输入：nums1 = [1], m = 1, nums2 = [], n = 0
//        输出：[1]
//         
//
//        提示：
//
//        nums1.length == m + n
//        nums2.length == n
//        0 <= m, n <= 200
//        1 <= m + n <= 200
//        -109 <= nums1[i], nums2[i] <= 109
//
//        来源：力扣（LeetCode）
//        链接：https://leetcode-cn.com/problems/merge-sorted-array
//        著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。